package com.liu.algorithm01;

import java.util.ArrayList;

public class BinarySearch04 {
    /*
        给你一个按照非递减顺序排列的整数数组nums，和一个目标值 target 。
        请你找出给定目标值在数组中的开始位置和结束位置。
        如果数组中不存在目标值 target，返回[-1，-1]。
        你必须设计并实现时间复杂度为 0(1ogn)的算法解决此问题。
    */
    public static void main(String[] args) {
        int[] arr = {1, 3, 3, 3, 5, 6};
        int[] ints = searchRange(arr, 3);
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < ints.length; i++) {
            list.add(ints[i]);
        }
        System.out.println(list);
    }

    // 方法1
    private static int[] searchRange(int[] a, int target) {
        int x = left(a,target);
        if (x == -1){
            return new int[]{-1,-1};
        }else {
            return new int[]{x,right(a,target)};
        }
    }

    // 方法2
    private static int left(int[] a, int target) {
        int low = 0;
        int high = a.length - 1;
        int candidate = -1;
        while (low <= high) {
            int mid = (low + high) >>> 1;
            long midVal = a[mid];
            if (target < midVal) {
                high = mid - 1;
            } else if (target > midVal) {
                low = mid + 1;
            } else {
                candidate = mid;
                high = mid - 1;
            }
        }
        return candidate;
    }
    private static int right(int[] a, int target) {
        int low = 0;
        int high = a.length - 1;
        int candidate = -1;
        while (low <= high) {
            int mid = (low + high) >>> 1;
            long midVal = a[mid];
            if (target < midVal) {
                high = mid - 1;
            } else if (target > midVal) {
                low = mid + 1;
            } else {
                candidate = mid;
                low = mid + 1;
            }
        }
        return candidate;
    }
}
